package com.hyper_yang.algorithmRecord.June;

import java.util.ArrayList;
import java.util.List;

// 2025.06.08 字典序排数
public class LeetCode_386 {
/*
给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
 */

    // 深度优先搜索:
    public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<>();
        // 从 1 到 9 开始遍历，作为递归的起点
        for (int i = 1; i <= 9; i++) {
            if (i <= n) { // 确保起始数字不超过 n
                dfs(i, n, result);
            }
        }
        return result;
    }

    private void dfs(int currentNum, int n, List<Integer> resultList) {
        // 如果当前数字超过 n，则停止递归
        if (currentNum > n) {
            return;
        }

        // 将当前数字添加到结果列表
        resultList.add(currentNum);

        // 尝试在当前数字后面追加 0 到 9
        for (int digit = 0; digit <= 9; digit++) {
            // 计算下一个数字
            int nextNum = currentNum * 10 + digit;
            // 如果下一个数字不超过 n，则继续递归
            if (nextNum <= n) {
                dfs(nextNum, n, resultList);
            } else {
                // 优化：如果 nextNum 已经大于 n，则后续的 digit 也会使 nextNum 更大，直接跳出循环
                break;
            }
        }
    }

    public static void main(String[] args) {
        LeetCode_386 solution = new LeetCode_386();
        solution.lexicalOrder(13).forEach( var -> System.out.print(var+" "));
        System.out.println();
        solution.lexicalOrder(2).forEach( var -> System.out.print(var+" "));
    }
}
